home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / cmln1185.arc / SORTING2.LTG < prev    next >
Text File  |  1986-02-27  |  5KB  |  114 lines
  1.  
  2.                             Listing 2
  3.  ì
  4. I) áOptional initialization of the priority array if the user wishes to
  5.     specify a particular sorting order. áThis is useful for defining
  6.     unusual character sort sequences such as: áA a B b C c ... Z z
  7.  ì
  8.         Loop from Byte_Priority = 1 to 256ì
  9.          áááPRIORITY(User_Defined_Byte_Value + 1) = Byte_Priorityì
  10.         End loop
  11.  ì
  12. II) Initialize the ordering array starting order, remembering to negate the
  13.     last element to initially define the entire set of records as one
  14.     subgroup.
  15.  ì
  16.         Loop from Record = 1 to Nì
  17.          áááORDER(Record) = Recordìè        End loopì
  18.         ORDER(N) = - ORDER(N)
  19.  ì
  20. III) Zero the 256 elements of the COUNT array
  21.  ì
  22.         Loop from Count_Location = 1 to 256ì
  23.          áááCOUNT(Count_Location) = 0ì
  24.         End loop
  25.  ì
  26. IV) áIf the records to be sorted are similar to floating point numbers
  27.      and the sign bit of the record is not the most significant bit of the
  28.      record, then it is necessary to do a presort on the sign of the data
  29.      records since that is the most significant part of a number and must 
  30.      be worked on first. áAny technique can be applied here that groups the 
  31.      records into two subgroups of positive and negative numbers making sure
  32.      to negate the ORDER elements at the ends of the two subgroups and
  33.      saving their subscript address values for later. áNote that for
  34.      ascending numeric sorts the top subgroup should contain positive
  35.      values and the bottom subgroup should contain negative values and vice
  36.      versa for descending sorts.
  37.  ì
  38. V) ááLoop through the data at most NBYTE times where NBYTE is the number of
  39.      bytes in a record. áStart work on the byte of greatest significance
  40.  ááááin value and proceed to the least significant byte. áNote that 
  41.      sometimes for the same computer language, the numeric data and
  42.      character data's least through most significant bytes are stored in 
  43.      reverse order.
  44.  
  45.      Loop from Working_Byte = 1 to NBYTE
  46.  
  47.          Va) Retrieve the current working byte from the N data records and
  48.              place them into the integer array IDATA. áNotice here that one
  49.              does not need to save the entire set of data records in main 
  50.              memory to use this sort algorithm, just the current byte values
  51.              in IDATA. áTo save even more memory, one could eliminate the
  52.              IDATA array and replace the Byte_Value assignments in steps 3
  53.              and 7 of the DISP-ADSORT routine. áThe replacement code may 
  54.              involve an individual byte retrieval routine from hard disk
  55.              storage.
  56.  ì
  57.         Loop from Record = 1 to Nì
  58.          áááIDATA(Record) = Current_Working_Byte(Record)ì
  59.         End loop
  60.  
  61.          Vb) Search through the ORDER array to locate subgroups of length
  62.              greater than one. áWhen a subgroup is found, call the DISP-ADSORT
  63.              routine. áFor very short subgroups it may be faster to use a
  64.              more efficient sort technique such as Insertion sort. áSince the
  65.              shorter subgroups are time consuming for DISP-ADSORT, this
  66.              hybrid scheme improves the efficiency of the sort tremendously.
  67.              The decision of which technique to choose is based on the
  68.              length of the subgroup and the timing advantages for a particular
  69.              implementation.
  70.  ì
  71.         Record = 1ìè        Loop While Record <= Nì
  72.          áááFirst_Record_of_Subgroup = Recordì
  73.          áááLoop While ORDER(Record) > 0ì
  74.          áááááááRecord = Record + 1ì
  75.          áááEnd loopì
  76.          áááLast_Record_of_Subgroup = Recordì
  77.          áááLength_of_Subgroup = 1 + Last_Record_of_Subgroup -ì
  78.          áááááááááááááááááááááááááááFirst_Record_of_Subgroupì
  79.          áááIf Length_of_Subgroup > 1ì
  80.          áááThenì
  81.          áááááááIf Length_of_Subgroup > Minimum_Lengthì
  82.          áááááááThenì
  83.          áááááááááááCall DISP-ADSORT Routineì
  84.          áááááááElseì
  85.          áááááááááááCall More_Efficient_Sort Routine (for thisì
  86.          áááááááááááááááááááááááááááááásingle byte subgroup)ì
  87.          áááááááEndifì
  88.          áááEndifì
  89.          áááRecord = Record + 1ì
  90.         End loop
  91.  
  92.      End of Working_Byte loop for step V.
  93.  
  94.  ì
  95. VI) ááReset the ORDER elements to positive values (reset sign bit) thereby
  96.       removing subgroup markers.
  97.  ì
  98.         Loop from Record = 1 to Nì
  99.          áááORDER(Record) = Absolute Value( ORDER(Record) )ì
  100.         End loop
  101.  ì
  102. VII) áIf the data records are numeric data types, then one may have to do a
  103.       post-sort to reverse the ordering of the lower sign subgroup. áThe
  104.       subgroup limits should be available from step IV above. áAny 
  105.       technique can be used that reverses the sequence of the ORDER elements
  106.       for the lower subgroup only. áApplication of an algorithm for this step
  107.       and step IV will depend on how floating point numbers are represented
  108.       in the computer and how the priority arrays have been set during
  109.       processing.
  110.  ì
  111. VIII) The sort is complete with the ordering currently stored in ORDER and
  112.       the original data contents left undisturbed. áOne may now return to
  113.       the calling program.
  114.